#
# @lc app=leetcode.cn id=218 lang=ruby
#
# [218] 天际线问题
#

# @lc code=start
# @param {Integer[][]} buildings
# @return {Integer[][]}
def get_skyline(buildings)
  buildings.sort! {
    |x, y|
    if x[0] == y[0]
      y[2] <=> x[2]
    else
      x[0] <=> y[0]
    end
  }

  result = Array.new(0) { Array.new(2) { 0 } }
  i = 0
  heap = EHeap.new
  while true
    inH = heap.peek
    outH = buildings[i]

    if inH == nil && outH == nil
      # end
      break
    end

    if inH == nil
      # 第一次遇到一个建筑
      # 推进去 建一个点
      result = result.append([outH[0], outH[2]])
      heap.push(outH)
      i += 1
      next
    end

    if outH == nil || inH[1] < outH[0]
      # 堆外的建筑没有关联
      # 如果这里peek出来的也是结束了的 是无效的
      while heap.peek != nil && heap.peek[1] <= inH[1]
        heap.pop
      end
      cur = heap.peek
      if cur == nil
        result = result.append([inH[1], 0])
      elsif cur[2] != inH[2]
        result = result.append([inH[1], cur[2]])
      end
      next
    elsif inH[1] == outH[0]
      while heap.peek != nil && heap.peek[1] <= inH[1]
        heap.pop
      end
      heap.push outH
      cur = heap.peek
      if cur[2] != inH[2]
        result = result.append([inH[1], cur[2]])
      end
      i += 1
    else
      heap.push outH
      if inH[2] < outH[2]
        result = result.append([outH[0], outH[2]])
      end
      i += 1
    end
  end

  return result
end

class EHeap
  attr_accessor :h, :cnt

  def initialize
    @h = []
    @cnt = 0
  end

  def peek
    if @cnt == 0
      return nil
    end
    return @h[0]
  end

  def pop
    _r = @h[0]
    @h[0] = @h[@cnt - 1]
    @cnt -= 1
    i = 0
    while i * 2 + 1 < @cnt
      l = 2 * i + 1
      r = 2 * i + 2
      t = l
      if r < @cnt && @h[r][2] > @h[l][2]
        t = r
      end
      if @h[i][2] >= @h[t][2]
        break
      end
      tmp = @h[i]
      @h[i] = @h[t]
      @h[t] = tmp
      i = t
    end
    return _r
  end

  def push(ele)
    @h[@cnt] = ele

    @cnt += 1
    idx = @cnt - 1
    while idx > 0
      _p = (idx - 1) / 2
      if @h[_p][2] < @h[idx][2]
        tmp = @h[idx]
        @h[idx] = @h[_p]
        @h[_p] = tmp
        idx = _p
      else
        break
      end
    end
  end
end

# @lc code=end

if __FILE__ == $0
  h = EHeap.new
  for s in [[5951, 42679, 584900], [7612, 460224, 165719], [10054, 528935, 547159], [12434, 184263, 538819], [14903, 205061, 507630], [30168, 640118, 643081], [52730, 67749, 544684], [56208, 347295, 318255], [57296, 500861, 788192], [65779, 535324, 564426], [69626, 936712, 415579], [77787, 785719, 327931], [82254, 805279, 920649], [86518, 383868, 930470], [87489, 418143, 10692], [98967, 724391, 93083], [99745, 742397, 134090], [101345, 176839, 627338], [116139, 360005, 261692], [118986, 130026, 582543], [122923, 470827, 554902], [123305, 124192, 200341], [125932, 726376, 657081], [137743, 889344, 943207], [143009, 468012, 356768], [144978, 404082, 31802], [146685, 244171, 473528], [152385, 835275, 67458], [159945, 571319, 499254], [160872, 908174, 692144], [164623, 315507, 76118], [177782, 386719, 229831], [180448, 787809, 497368], [186034, 256757, 542791], [188402, 843895, 494935], [197303, 894782, 801283], [202312, 261398, 307960], [202390, 308850, 114020], [216466, 587906, 560282], [254738, 444539, 769109], [275954, 456722, 435187], [278192, 586784, 83534], [279840, 472712, 598594], [287433, 876565, 846065], [318879, 922949, 183256], [337738, 845315, 912970], [344100, 965430, 103653], [350296, 779286, 126824], [366521, 400209, 4075], [367676, 911181, 784590], [371269, 947782, 560479], [377942, 978066, 660521], [402938, 794535, 521823], [407536, 929952, 795747], [409959, 457637, 251645], [417770, 838407, 530482], [425965, 790228, 56305], [439707, 961265, 137333], [446176, 513487, 141989], [455879, 582111, 663768], [472532, 567342, 107840], [492380, 561017, 757035], [497930, 603380, 454255], [504632, 534547, 694128], [512389, 594618, 356728], [520832, 931989, 768018], [525637, 997553, 817328], [535984, 566145, 926744], [569708, 631488, 207038], [583058, 918142, 600957], [583928, 806005, 34478], [591010, 851424, 292990], [608726, 998069, 42301], [610001, 658217, 97268], [615495, 785912, 300917], [650994, 896338, 60267], [693313, 726376, 583178], [706898, 791076, 724417], [709816, 928183, 750769], [719093, 753014, 698100], [720242, 773502, 113359], [742290, 807067, 286960], [754791, 832571, 262145], [763308, 855300, 66229], [785215, 909931, 2177], [787290, 818298, 269345]]
  # for s in [[57296, 500861, 788192],779, 535324, 564426], [69626, 936712, 415579], [77787, 785719, 327931], [82254, 805279, 920649], [86518, 383868, 930470], [87489, 418143, 10692], [98967, 724391, 93083], [99745, 742397, 134090], [101345, 176839, 627338], [116139, 360005, 261692], [118986, 130026, 582543], [122923, 470827, 554902], [123305, 124192, 200341], [125932, 726376, 657081], [137743, 889344, 943207], [143009, 468012, 356768], [144978, 404082, 31802], [146685, 244171, 473528], [152385, 835275, 67458], [159945, 571319, 499254], [160872, 908174, 692144], [164623, 315507, 76118], [177782, 386719, 229831], [180448, 787809, 497368], [186034, 256757, 542791], [188402, 843895, 494935], [197303, 894782, 801283], [202312, 261398, 307960], [202390, 308850, 114020], [216466, 587906, 560282], [254738, 444539, 769109], [275954, 456722, 435187], [278192, 586784, 83534], [279840, 472712, 598594], [287433, 876565, 846065], [318879, 922949, 183256], [337738, 845315, 912970], [344100, 965430, 103653], [350296, 779286, 126824], [366521, 400209, 4075], [367676, 911181, 784590], [371269, 947782, 560479], [377942, 978066, 660521], [402938, 794535, 521823], [407536, 929952, 795747], [409959, 457637, 251645], [417770, 838407, 530482], [425965, 790228, 56305], [439707, 961265, 137333], [446176, 513487, 141989], [455879, 582111, 663768], [472532, 567342, 107840], [492380, 561017, 757035], [497930, 603380, 454255], [504632, 534547, 694128], [512389, 594618, 356728], [520832, 931989, 768018], [525637, 997553, 817328], [535984, 566145, 926744], [569708, 631488, 207038], [583058, 918142, 600957], [583928, 806005, 34478], [591010, 851424, 292990], [608726, 998069, 42301], [610001, 658217, 97268], [615495, 785912, 300917], [650994, 896338, 60267], [693313, 726376, 583178], [706898, 791076, 724417], [709816, 928183, 750769], [719093, 753014, 698100], [720242, 773502, 113359], [742290, 807067, 286960], [754791, 832571, 262145], [763308, 855300, 66229], [785215, 909931, 2177], [787290, 818298, 269345]]
    h.push s
  end

  p "#{h.h}"

  while h.peek != nil
    p "pop: #{h.pop}"
  end
end
